//题目:
// 给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
// 在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。
// 路径的积是沿路径访问的单元格中所有整数的乘积。
// 返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。
// 注意，取余是在得到最大积之后执行的。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码
class Solution 
{
public:
    int maxProductPath(vector<vector<int>>& grid) 
    {
        int m=grid.size(),n=grid[0].size();
        //1.创建dp表————dp[i][j]表示：来到grid[i][j]的所有路径的积
        vector<vector<set<long long>>> dp(m,vector<set<long long>>(n));
        //2.初始化
        int sum1=1,sum2=1;
        for(int i=0;i<m;i++) sum1*=grid[i][0],dp[i][0].insert(sum1);
        for(int j=0;j<n;j++) sum2*=grid[0][j],dp[0][j].insert(sum2);
        //3.填表————dp[i][j]=dp[i][j-1] $ dp[i-1][j];
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                for(auto x:dp[i][j-1])
                    dp[i][j].insert(x*grid[i][j]); 
                for(auto x:dp[i-1][j])
                    dp[i][j].insert(x*grid[i][j]);   
            }
        }
        //4.确定返回值
        long long ret=-1,MAX_VALUE=1e9+7;
        for(auto x:dp[m-1][n-1]) if(x>=0) ret=max(ret,x);
        return ret%MAX_VALUE;
    }
};